package algorithm.graph;

import java.util.Iterator;

//获取联通分量
public class Component {
    //图
    private Graph graph;
    //是否被访问过
    private boolean[] visited;
    //联通分量的个数
    private int ccount;

    private int[] id;

    public Component(Graph graph) {
        this.graph = graph;
        this.visited = new boolean[graph.V()];

        for (int i = 0; i < graph.V(); i++) {
            id[i] = -1;
        }

        for (int i = 0; i < graph.V(); i++) {
            if (!visited[i]){
                dfs(i);
                ccount++;
            }
        }
        System.out.println("OK");
    }

    private void dfs(int v) {

        visited[v]=true;
        id[v]=ccount;
        Iterator<Integer> iterator = graph.iterator(v);
        while (iterator.hasNext()){
            Integer value = iterator.next();
            if (!visited[value]){
                dfs(value);
            }
        }

    }

    public int count(){
        return ccount;
    }


    public static void main(String[] args) {
        // TestG1.txt
        String filename1 = "testG1.txt";
        Graph graph1 = ReadGraph.readGraph(SparseGraph.class, filename1);
        Component component1 = new Component(graph1);
        System.out.println("TestG1.txt, Component Count: " + component1.count());
        System.out.println();

        // TestG2.txt
        String filename2 = "testG2.txt";
        Graph graph2 = ReadGraph.readGraph(SparseGraph.class, filename2);
        Component component2 = new Component(graph2);
        System.out.println("TestG2.txt, Component Count: " + component2.count());
    }
}
